package com.vint.lintcode;

import com.vint.common.ListNode;

/**
 * 翻转链表2，翻转一个区间内的子链表，简单
 */
public class Lintcode36 {
	public ListNode reverseBetween(ListNode head, int m, int n) {
		if (null == head || m == n) {
			return head;
		}
		if( 1 != m) {
			ListNode m1Node = getKListNode(head, m - 1);
			ListNode mNode = m1Node.next;
			ListNode nNode = getKListNode(head, n);
			ListNode n1Node = nNode.next;
			nNode.next = null;

			ListNode rHead = reverse(mNode);
			m1Node.next = rHead;
			ListNode tail = getTail(rHead);
			tail.next = n1Node;
			return head;
		} else {
			ListNode mNode = head;
			ListNode nNode = getKListNode(head, n);
			ListNode n1Node = nNode.next;
			nNode.next = null;

			ListNode rHead = reverse(mNode);
			ListNode tail = getTail(rHead);
			tail.next = n1Node;
			return rHead;
		}
	}
	public ListNode getTail(ListNode head) {
		if (null == head || null == head.next) {
			return head;
		}
		ListNode tail = head;
		while (null != tail.next) {
			tail = tail.next;
		}
		return tail;
	}
	public ListNode getKListNode(ListNode head, int k) {
		int start = 1;
		if (null == head) {
			return head;
		}
		ListNode visit = head;
		while (null !=visit && start != k) {
			visit = visit.next;
			start++;
		}
		return visit;
	}
	public ListNode reverse(ListNode head) {
		if (null == head || null == head.next) {
			return head;
		}
		ListNode newHead = head;
		ListNode walk = head.next;
		newHead.next = null;
		while (null != walk) {
			ListNode nextWalk = walk.next;
			walk.next = newHead;
			newHead = walk;
			walk = nextWalk;
		}
		return newHead;
	}

}
